<?php

/**
 * Created by PhpStorm.
 * User: JackWang
 * Date: 2022/4/20
 * Time: 15:29
 */
class Sort
{
    public function maoPaoSort(array $array)
    {
        $length = count($array);
        if ($length <= 0) {
            return [];
        }
        for ($i = 0; $i < $length - 1; $i++) {
            for ($j = 0; $j < $length - $i - 1; $j++) {
                if ($array[$j] > $array[$j + 1]) {
                    $temp = $array[$j];
                    $array[$j] = $array[$j + 1];
                    $array[$j + 1] = $temp;
                }
            }
        }
        return $array;
    }

    public function changeSort(array $array)
    {
        $length = count($array);
        if ($length <= 0) {
            return [];
        }
        for ($i = 0; $i < $length - 1; $i++) {
            $maxKey = $i;
            for ($j = $i; $j < $length; $j++) {
                if ($array[$maxKey] < $array[$j]) {
                    $maxKey = $j;
                }
            }
            if ($maxKey != $i) {
                $temp = $array[$maxKey];
                $array[$maxKey] = $array[$i];
                $array[$i] = $temp;
            }
        }
        return $array;
    }

    public function insertSort(array $array)
    {
        $length = count($array);
        if ($length <= 0) {
            return [];
        }
        for ($i = 0; $i < $length; $i++) {
            $key = $i - 1;
            $value = $array[$i];
            while ($key > 0 && $array[$key] > $value) {
                $array[$key + 1] = $array[$key];
                $key--;
            }
            $array[$key + 1] = $value;
        }
        return $array;
    }

    public function quickSort(array $array)
    {
        $length = count($array);
        if ($length <= 1) {
            return $array;
        }
        $left = $right = [];
        for ($i = 1; $i < $length; $i++) {
            if ($array[$i] > $array[0]) {
                $right[] = $array[$i];
            } else {
                $left[] = $array[$i];
            }
        }
        $leftArr = $this->quickSort($left);
        $rightArr = $this->quickSort($right);
        return array_merge($leftArr, [$array[0]], $rightArr);
    }

    public function halfFind($x, array $array)
    {
        $length = count($array);
        if ($length < 0) {
            return -1;
        }
        $min = 0;
        $max = $length - 1;
        while ($min <= $max) {
            $middle = floor(($min + $max) / 2);
            if ($x > $array[$middle]) {
                $min = $middle + 1;
            } elseif ($x < $array[$middle]) {
                $max = $middle - 1;
            } else {
                return $middle;
            }
        }
        return -1;
    }
}

$sort = new Sort();

$arr = [1, 10, 6, 5, 7, 3, 4, 9, 8, 2];

$temp1 = $sort->maoPaoSort($arr);
$temp2 = $sort->changeSort($arr);
$temp3 = $sort->insertSort($arr);
$temp4 = $sort->quickSort($arr);

$x = $sort->halfFind(10, $temp4);

echo $x;

